package cn.talins.algorithm.utils;

import java.util.List;

/**
 * 索引树
 * @author talins
 */
public class IndexTree {

    private final int[] tree;
    private final int n;

    public IndexTree(List<Integer> list) {
        n = list.size();
        tree = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            add(i, list.get(i - 1));
        }
    }

    public int sum(int start, int end) {
        validate(start, end);
        return sum(end + 1) - sum(start);
    }

    private int sum(int index) {
        int ret = 0;
        while (index > 0) {
            ret += tree[index];
            index -= index & -index;
        }
        return ret;
    }

    public void add(int index, int d) {
        validate(index, n);
        while (index <= n) {
            tree[index] += d;
            index += index & -index;
        }
    }

    private void validate(int start, int end) {
        if (start < 0 || end > n || start > end) {
            throw new IllegalArgumentException("Invalid range");
        }
    }
}
